Over the past several decades, integrated circuits (ICs) have become an integral part of modem electrical devices. Rather than using "off-the-shelf" components, it is often desirable to use custom or semi-custom ICs. To permit easier circuit design of custom or semi-custom ICs to fulfill specific performance constraints or circuit requirements and to aid in circuit fabrication, automated systems for design and manufacturing have been developed. Automated design systems are also widely used to design highly complex ICs and ICs having short life cycles.
One type of computer aided design (CAD) system is known as a "behavioral synthesis system." With such a system, the inputs, outputs and other circuit parameters are input into a computer using a hardware description language (HDL). Behavioral synthesis software then designs a circuit meeting these parameters.
A typical integrated circuit design and manufacturing process using behavioral synthesis begins with certain performance or structural constraints. A description of these constraints is made using an HDL such as VHDL or VERILOG which are commercially available behavioral synthesis languages. This HDL can be manipulated to form a "netlist" (i.e. a list of "nets") specifying components and their interconnections which meet the circuit constraints. However, the actual placement plan of components on wafers and the topography of the wiring connections is reserved for a subsequent "layout" stage.
A conventional method 10 for fabricating an integrated circuit is outlined in a flowchart in FIG. 1 beginning at a step 12. In a step 14, a set of circuit specifications is developed. Generally, these specifications can include the overall integrated circuit performance and also specific size and placement characteristics of components on a chip.
A circuit designer will create a description of these specifications in a step 16 using a hardware description language (HDL). Common hardware description languages include the aforementioned VHDL and VERILOG although any suitable language (such as a proprietary HDL) may be used. The HDL description of the specifications is then used in a step 18 to synthesize a netlist. The netlist may also be described in the hardware description language (HDL). A step 20 verifies the behavior and functionality of the netlist, and allows for the repeating of steps 16 and 18 if the behavior and functionality do not meet specifications.
As noted above, the netlist specifies which components (known as "cells" or "modules") will be connected but does not specify the precise wiring topography. A cell has one or more "pins" for interconnection with pins of other cells. The "netlist" therefore includes "nets" which define the connectivity between pins of the cells. In other words, a "net" is a set of electrically equivalent pins of a number of cells, which must be connected together to form a common electrical node. Components or cells described by the netlist will form a circuit satisfying the circuit specifications.
Further referring to the conventional process of FIG. 1, the circuit designer transfers the verified netlist description into a layout tool in a step 24. The layout step 24 performed by the layout tool determines the actual physical placement of cells on the "layout area" of integrated circuit die or chip to form an array of gates or standard cells. The "layout area" is the area designated for the active components of the IC. The "placement" step of the layout process is extremely time consuming, as it can take several days of computation on a computer workstation for ICs having several hundred thousands of gates. The actual routing of connections or "wires" between pins of the cells is also determined in layout step 24.
Caltech Intermediate Format (C.I.F.) data created in the step 24 is transferred in a step 26 to a mask fabrication tool where an integrated circuit mask is created. This mask will be used to create the integrated circuit chip or die. This mask is generated on a machine equipped to read C.I.F. data. This C.I.F. data can be transferred to this machine through a hard disk, magnetic tape, a floppy disk, or other transmission medium. It is also possible for the mask generating machine to be part of or the same machine that synthesizes the netlist.
An integrated circuit is produced in a step 28. A conventional method of producing the circuit is to use the mask created in step 26 in photolithography processes. Once the chip itself has been fabricated, the integrated circuit on the die must have connections to external circuitry. This is generally accomplished by attaching bonding wires and/or lead frames to the integrated circuit. The circuit is then encapsulated in packaging materials such as plastic. The design and fabrication of the integrated circuit is completed at this point, as indicated at 30.
After the placement, if some of the constraints, such as timing requirements, are not met, the designer may change the netlist by adding some new cells (i.e. components) into the netlist or by replacing some of the existing cells by, typically, bigger cells. The problem encountered in the prior art is how to place the new or modified cells on the layout area such that the original placement of the other cells are minimally disturbed and the timing requirements are met. This problem is called ECO (Engineering Change Order) placement problem. In particular, it is hoped that the ECO will not require the placement step to be repeated because, as mentioned above, it is extremely time consuming.
Although the problem of ECO placement is very well-known and important in VLSI physical design, not much research has been done in this area. At the present time, there is no known published research work on the problem. Traditionally, ECO placement problem has been addressed using a very simple heuristic approach. Some of the industry tools use this simple approach to do the ECO placement. The heuristic works as follows:
(i) For gate array designs, try to place each new or changed cell in an empty base site close to a cell that shares a common net. If no such site found, place it in any empty legal site. PA1 (ii) For standard cell designs, place each new cell at the end of a row with smaller row length. For each changed cell, place it in the same row and location by "pushing aside" (if necessary) the rest of the cells in the row so as to remove overlap of cells.
As noted above, the main objective of the ECO placement is to meet the timing requirements of circuits. The above mentioned heuristic approaches of the prior art, however, does not take the timing constraints into consideration. It is only with good luck that the ECO placements using the heuristics of the prior art would accomplish the desired timing constraints. This could require a completely new iteration of the layout process (including the placement step ) with many days of lost time.
A limited amount of prior art uses iterative placement improvement algorithms to place cells; however, these algorithms only work for row-based designs, i.e. these algorithms may not be used for non-row-based designs. "Domino" is an example of an iterative placement improvement algorithm which only works for row-based designs. "Iterative Placement Improvement by Network Flow Methods," IEEE Transactions Computer-Aided Design, vol. 13, no. 10, pp. 1189-2000, October 1994 by K. Doll, F. M. Johannes, and K. J. Antreich. As Domino does not work for non-row-based designs, ECO placement improvement for non-row-based designs are addressed using the above mentioned heuristic approaches.